/*
题目描述：正则表达式匹配
方法：
1. pattern下一个字符不为 '*'
   如果 pattern 当前字符和str当前字符相同，或者 pattern 当前字符为 '.'
   str 和 pattern 向前推进一个字符
   否则返回false
2. pattern下一个字符为 '*'
   如果 pattern 当前字符和str当前字符相同，或者 pattern 当前字符为 '.'，有三种匹配策略
   (1) str 向前推进一个字符，pattern 向前推进两个字符
   (2) str 向前推进一个字符， pattern 不懂保持原状态，以便匹配更多相同字符
   (3) str 保持不动， pattern 向前推进两个字符， 舍弃 a*, 此时 '*'表示0个字符

注意：在Java中应该时刻检查数组越界问题！
 */
public class E19 {
    public static void main(String[] args) {
        char[] str = {'a', 'a', 'a'};
        char[] pattern = {'a', 'a','.','a'};

        boolean res =  match(str, pattern);

        System.out.println(res);
    }

    public static boolean match(char[] str, char[] pattern){
        if(str == null || pattern == null){
            return false;
        }
        return matchCore(str, pattern, 0, 0);
    }

    public static boolean matchCore(char[] str, char[] pattern, int strIndex, int patternIndex){
        if(strIndex == str.length && patternIndex == pattern.length){
            return true;
        }
        if(strIndex != str.length && patternIndex == pattern.length){
            return false;
        }
        if((patternIndex + 1 < pattern.length) && pattern[patternIndex + 1] == '*'){
            if((strIndex < str.length && pattern[patternIndex] == str[strIndex]) || (strIndex < str.length && pattern[patternIndex] == '.')){
                return matchCore(str, pattern, strIndex + 1, patternIndex + 2)
                        || matchCore(str, pattern, strIndex + 1, patternIndex)
                        || matchCore(str, pattern, strIndex, patternIndex + 2);
            }
            else{
                return matchCore(str, pattern, strIndex, patternIndex + 2);
            }
        }

        if((strIndex < str.length && pattern[patternIndex] == str[strIndex]) || (strIndex < str.length && pattern[patternIndex] == '.')){
            return matchCore(str, pattern, strIndex + 1, patternIndex + 1);
        }
        return false;
    }
}
